1. Field of the Invention
The present invention relates to an associative memory system to be mounted on a processor or to constitute peripheral circuits of the processor.
2. Description of the Prior Art
For a system using a microprocessor, the address space to be actually used is limited by the physical number of memory cells to be mounted. The limited address space outside the microprocessor is called a physical address space and the address is called a physical address. However, because the address space is not physically limited inside the microprocessor, various processings are executed by assuming that addresses equal to or more than the actual address space are present. The address space inside the microprocessor is called a virtual address space and the address is called a virtual address.
Therefore, when a microprocessor uses an outside memory space, it has to convert the virtual address in the microprocessor into a physical address. The circuit used for the conversion is called a translate look aside buffer circuit (hereafter referred to as a TLB circuit). The TLB circuit is first described below.
FIG. 8 shows a block diagram of the TLB circuit. In FIG. 8, numeral 2 is a memory circuit called a content addressable memory circuit (hereafter referred to as a CAM circuit), 71 is a normal memory circuit, 72 is an address signal of the CAM circuit, 5 is a hit signal (output line) outputted from the CAM circuit 2, 4 is a virtual address, and 65 is a physical address. Though the memory circuit 71 performs the completely same operation as the normal memory circuit, the word selection signal of the normal memory circuit is connected with the hit signal 5 outputted from the CAM circuit 2. Therefore, the memory circuit 71 does not need to generate the word selection signal with a decoder circuit unlike the normal memory circuit or does not have the decoder circuit.
The circuit called CAM circuit has a function for checking if the stored data coincides with external data in addition to the function for storing or reading data from the outside line the normal memory circuit, which is a type of the memory circuit called associative memory. When the CAM circuit stores the data coinciding with external data, it has a function for outputting a signal called hit signal and notifying the outside in which word the data coinciding with external data is stored.
FIG. 9 is an internal block diagram for explaining the CAM circuit 2. In FIG. 9, numeral 41 is a CAM cell circuit constituting the CAM circuit, 31 is supply potential, 35 is a word selection signal, 81 is a decoder circuit, and 82 is a data read/write circuit. FIG. 3 is an internal block diagram explaining the CAM cell circuit in detail. Numeral 31 is supply potential, 32a and 32b are resistances, 33a to 33h are n-channel transistors, 34 is earth potential, 35 is a word selection signal, 36 is a coincidence signal, 37 is a bit line of external data to be compared, 39 is a bit line of stored data, and 40 is a bit line of reverse data of stored data. The CAM cell circuit 41 can store data because it is a memory circuit. In FIG. 3, numeral 390 is a stored data value, 400 is a reverse data value of stored data. The coincidence signal 36 comes to the supply potential when the data 390 in the CAM cell circuit 41 coincides with the external-data bit line data 37. In FIG. 9, the horizontal direction is assumed as the bit direction and the vertical direction is assumed as the word direction. The coincidence signal 36 in FIG. 3 equals the hit signal 5 of the CAM circuit 2 in FIG. 8.
The operation for the CAM circuit 2 to store data is the same as that of the normal memory circuit. To store the data in the CAM cell circuit 41 of the CAM circuit 2, the data in the bit lines 39 and 40 is stored in a circuit comprising the n-channel transistors 33c and 33d and the resistances 32a and 32b through the n-channel transistors 33a and 33b selected by the word selection signal 35. That is, the data in the bit line 39 is written the data value 390 and the data in the bit line 40 is written the data value 400. To read the data in the CAM cell circuit 41 of the CAM circuit 2 to the outside, the data in the data values 390 and 400 is transferred to the bit lines 39 and 40 through the n-channel transistors 33a and 33b selected by the word selection signal 35 and read to the outside from the data read/write circuit 82. These operations are controlled and executed by the decoder circuit 81 and data read/write circuit 82. This is the same as the normal memory circuit.
Then, the operation for the CAM circuit 2 to compare data is described below. To simplify the description, it is assumed that the supply potential indicates the logical value "1" and the earth potential indicates the logical value "0". When the circuit is connected to both the supply potential and earth potential, it is assumed that the logical value indicates "0". The coincidence signal 36 normally has the logical value "1" because it is connected to the supply potential 31 as shown in FIG. 9.
When it is assumed that the data "1" is stored in the CAM cell circuit 41, the data value 390 in FIG. 3 is "1" (therefore, the reverse data value 400 is "0"). When the external data to be compared is "1", the bit line 37 of external data is set to "1" (the reverse bit line 38 of external data is set to "0"). In this case, the n-channel transistors 33e and 33h in pairs of the n-channel transistors 33e and 33g on one hand and 33f and 33h on the other are turned off and the coincidence signal 36 is connected with the supply potential 31 which is not connected with the earth potential 34. When the data "0" is stored in the CAM cell circuit 41 and the data to be compared is "0", the coincidence signal 36 is connected with the supply potential 31 which is not connected with the earth potential 34. In FIG. 9, when every bit-directional CAM cell circuit 41 is equal to the external data to be compared of each bit, the hit signal 5 (equal to the coincidence signal 36) has the logical value "1" because it is not connected with the earth potential 34 as described above. That is, because the data coinciding with external data as the result of comparison is present in the CAM circuit 2, the hit signal 5 showing that data is present has the logical value "1".
On the contrary, even if one bit having unequal data is present in the bit-directional CAM cell circuits, the both n-channel transistors of either of pairs of the n-channel transistors 33e and 33g on one hand and 33f and 33h on the other are turned on in the CAM cell circuits 41. Therefore, the coincidence signal 35 is connected with both the earth potential 34 and the supply potential 31 in the CAM cell circuits 41. In this case, the hit signal 5 in FIG. 8 has the logical value "0" as defined. As the result of comparing the data stored in any word with external data, the hit signal 5 of the word indicates the data "1" if they are equal to each other but it indicates the data "0" if they are not equal. Because different data is stored in each word in the CAM circuit 2, only any one of bit signals 5 is set to "1" or all bit signals 5 are set to "0". However, no hit signal 5 is set to "1" in two or more words.
The operation of the TLB circuit is described below by referring to FIG. 8 according to the above mentioned. &lt;1&gt; In FIG. 8, the data in the virtual address 4 is stored in any word of the CAN circuit 2 and the physical address to be converted is stored in equal words in the memory circuit 71. &lt;2&gt; It is checked if data coinciding with the data in the virtual address 4 given from the outside is present in each word of the CAM circuit 2. &lt;3&gt; If coincident data is present in the CAM circuit 2, the hit signal 5 of the coincident word comes to "1". &lt;4&gt; Because the hit signal 5 is connected to the word selection line of the memory circuit 71, the physical address stored in the word in the memory circuit 71 is read and virtual-to-physical address conversion is completed when the hit signal 5 comes to "1". &lt;5&gt; Unless any coincident data is present in the above Item &lt;3&gt;, no physical address is read from the memory circuit 71 because no hit signal 5 comes to "1". The above mentioned is the address conversion method by the TLB circuit. However, the operation by the TLB circuit is normally slow because the operation of the CAM circuit 2 is slow.
Recent systems using a microprocessor normally use a memory having a structure of two or more hierarchies. In general, a memory cell to be directly accessed by a microprocessor comprises a semiconductor cell. In this case, a large-capacity low-speed dynamic RAM (hereafter referred to as DRAM) and a small-capacity high-speed static RAM (hereafter referred to as SRAM) are used. FIG. 10 shows a normal system constitution. In FIG. 10, numeral 51 is a microprocessor, 52 is an SRAM circuit, 53 is a DRAM circuit, 54 is an address, 55 is data, and 56 is a comparison circuit.
Data required by the microprocessor 51 is normally stored in the DRAM circuit 53 with a large capacity and some pieces of the data frequently used is stored in the SRAM circuit 52 capable of executing high-speed operation. The microprocessor 51 frequently uses the data stored in the SRAM circuit 52. It uses the data stored in the DRAM circuit 53 at a low speed only when using data not stored in the SRAM circuit 52. With the above constitution, the system operates at a high speed as if it uses a large-capacity high-speed memory cell. In this case, the SRAM circuit 52 is called cache memory and the DRAM circuit 53 is called main memory.
A cache memory comprises two SRAM circuits in order to judge whether or not necessary data is present in the cache memory. The two circuits are the SRAM circuit 52a for data and the SRAM circuit 52b for tag as shown in FIG. 10. The SRAM circuit 52a stores the data to be processed by the microprocessor 51 in its main memory similarly to the normal memory circuit. The SRAM circuit 52b for tag stores the high-order bits of an address. For example, if the address is expressed by 32-bit data, some bits starting with the highest order are stored in the SRAM circuit 52b for tag as a tag when the cache is assessed by low-order 16 bits.
The fact that necessary data is present in the cache is called "to hit the cache". For example, when it is found that the tag data read from the SRAM circuit 52b for tag by the address data of low-order 16 bits coincides the address data of its own high-order bits as the result of comparison by the comparison circuit 56, the comparison result represents that necessary data is present in the cache. If the former does not coincide with the latter, the comparison result represents that no necessary data is present in the cache. In this case, it is necessary to read data from the main memory. It is possible to use the abovementioned CAM circuit for the hit judgment of the cache tag. However, the CAM circuit is not used because it has a very large capacity compared with the TLB circuit and its operation is very slow.
As described above, the TLB circuit and cache memory circuit are essential for the memory control system of the systems using a microprocessor. The cache memory and main memory are normally accessed with a physical address because they are set outside the microprocessor. The memory control system using the TLB circuit is described below. FIG. 11 shows the constitution of a normal memory control system using a TLB circuit. In FIG. 11, numeral 51 is a microprocessor, 61 is a TLB circuit, 52 is a cache memory, 63 is a main memory, 61 is a virtual address, 65 is a physical address, and 66 is data.
Because the operation of the TLB circuit 61 is very slow as described above, the constitution in FIG. 11 has a problem. That is, though the cache memory 62 is used in addition to the main memory 63 to access memory data from the microprocessor 51 at a high speed in the system, it is necessary to access the low-speed TLB circuit 61 before accessing the cache memory 62.
Therefore, the method shown in FIG. 12 is frequently used to avoid the delay in the TLB circuit. In FIG. 12, numeral 8 is a hit signal, 51 is a microprocessor, 55 is a comparison circuit, 61 is a TLB circuit, 62a is a memory for cache data, 62b is cache tag, 4 is a virtual address, and 65a and 65b are physical addresses. No physical address is connected to the cache memory 62 but the virtual address 4 outputted from the microprocessor 51 is connected to it. Therefore, a physical address converted from the virtual address is stored in the cache tag 62b by using the virtual address as an address value. For FIG. 11, a physical address has been stored in the cache tag 62b by using the physical address as an address value.
The operation is described below. The TLB circuit 61 converts a virtual address into a physical address as usual and the physical address 65a read out of the cache tag with a virtual address by the cache memory is compared with the physical address 65b outputted by the TLB circuit 61. When two pieces of data coincide with each other, the hit signal 8 is set to "1". This shows that the physical address has been present in the TLB circuit 61 and necessary data is present in the cache memory 62.
The above mentioned is brief description of the memory control system. Details are disclosed in the following theses. "2.6 Gbyte/sec bandwidth Cache/TLB Macro for High-Performance RISC Processor" (IEEE CICC 91 pp. 10.2.1-10.2.4) "An In-Cache Address Translation Mechanism" (The 13th Annual International Symposium on Computer Architecture pp. 358-365)
As described above, the existing associative memory system takes time in generating the hit signal because it separately reads the data in the TLB circuit and the data in the cache tag before comparing these pieces of data with the comparison circuit to judge the hit of the cache memory.